//给定一个二叉树，我们在树的节点上安装摄像头。
//
// 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
//
// 计算监控树的所有节点所需的最小摄像头数量。
//
//
//
// 示例 1：
//
//
//
// 输入：[0,0,null,0,0]
//输出：1
//解释：如图所示，一台摄像头足以监控所有节点。
//
//
// 示例 2：
//
//
//
// 输入：[0,0,null,0,null,0,null,null,0]
//输出：2
//解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
//
//
// 提示：
//
//
// 给定树的节点数的范围是 [1, 1000]。
// 每个节点的值都是 0。
//
//
// Related Topics 树 深度优先搜索 动态规划 二叉树 👍 597 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function minCameraCover(root: TreeNode | null): number {

    /** 0-无覆盖， 1-有摄像头， 2-有覆盖 */
    function recur(node: TreeNode | null): statusCode {
        if (node === null) return 2;
        //? 后序遍历取了左孩子的返回值，右孩子的返回值，即left 和 right， 以后推导中间节点的状态
        const left: statusCode = recur(node.left),
            right: statusCode = recur(node.right);
        let resStatus: statusCode = 0;
        //? 此时子节点起码有一个没有被覆盖 则去父节点就该放摄像头
        if (left === 0 || right === 0) {
            resStatus = 1;
            resCount++;
            //? 左右有一个摄像头 则父必能被覆盖
        } else if (left === 1 || right === 1) {
            resStatus = 2;
            //? 其余情况则无覆盖
        } else {
            resStatus = 0;
        }
        return resStatus;
    }

    type statusCode = 0 | 1 | 2;
    let resCount: number = 0;
    if (recur(root) === 0) resCount++; //? 如果根无覆盖则需要再加一个摄像头
    return resCount;
};
//leetcode submit region end(Prohibit modification and deletion)
